

# 494.目标和

def findTargetSumWays(nums, target):
    if sum(nums)<abs(target):
        return 0
    if (sum(nums) + target) % 2 != 0:
        return 0
    else:
        weight = (sum(nums) + target) // 2
        dp = [[None] * (weight + 1) for _ in range(len(nums))]
        zeronumbers = 0
        for i in range(0, len(nums)):
            if nums[i] == 0:
                zeronumbers = zeronumbers + 1
            dp[i][0] = pow(2,zeronumbers)
        for j in range(1, weight + 1):
            if nums[0] == j:
                dp[0][j] = 1
            else:
                dp[0][j] = 0
        for i in range(1, len(nums)):
            for j in range(1, weight + 1):
                if nums[i] > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]
        return dp[len(nums) - 1][weight]

if __name__ == "__main__":
    nums = [0,0,0,0,0,0,0,0,1]
    target = 1
    result = findTargetSumWays(nums,target)
    print(result)